package com.sicheng.蓝桥.练习题.线段树;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/4 17:07
 */
public class SegmentTree {
    public static void main(String[] args) {
        SegmentTree segmentTree = new SegmentTree();
        int t = segmentTree.scanner.nextInt();


        while (t-- > 0) {
            int n = segmentTree.scanner.nextInt();
            int m = segmentTree.scanner.nextInt();
            //memset(tree,-1,sizeof(tree));//区间改值用-1
            segmentTree.build(1, 1, n);//建树
            for (int i = 1; i <= m; i++) {
                int p, x, y, a, b;
                p = segmentTree.scanner.nextInt();
                if (p == 1) {
                    System.out.println("**************单点查询操作**************");
                    x = segmentTree.scanner.nextInt();
                    System.out.println(segmentTree.ask_point(1, x));//单点查询,输出第x个数
                } else if (p == 2) {
                    System.out.println("**************单点修改操作**************");
                    x = segmentTree.scanner.nextInt();
                    y = segmentTree.scanner.nextInt();
                    segmentTree.change_point(1, x, y);//单点修改
                } else if (p == 3) {
                    System.out.println("**************区间查询操作**************");

                    a = segmentTree.scanner.nextInt();
                    b = segmentTree.scanner.nextInt();
                    System.out.println(segmentTree.ask_interval(1, a, b));//区间查询
                } else if (p == 4) {
                    System.out.println("**************区间修改操作**************");
                    a = segmentTree.scanner.nextInt();
                    b = segmentTree.scanner.nextInt();
                    y = segmentTree.scanner.nextInt();
                    segmentTree.changeadd_interval(1, a, b, y);
                } else {
                    System.out.println("**************区间改值操作**************");
                    a = segmentTree.scanner.nextInt();
                    b = segmentTree.scanner.nextInt();
                    y = segmentTree.scanner.nextInt();
                    segmentTree.changeupdate_interval(1, a, b, y);
                }
            }
        }
    }

    static class node {
        int l, r, w, lazy;//tree的l,r表示数组区间[l,r],w表示[l,r]区间和
    }

    node[] tree = new node[100000];
    Scanner scanner = new Scanner(System.in);

//lazy!=0是加值,lazy!=-1是改值

    void build(int v, int l, int r) {
        //建树,v表示tree里第v个结点,tree是完全二叉树
        tree[v].l = l;
        tree[v].r = r;
        if (tree[v].l == tree[v].r) {
            tree[v].w = scanner.nextInt();
            return;
        }
        int mid = (l + r) / 2;
        build(v * 2, l, mid);
        build(v * 2 + 1, mid + 1, r);
        tree[v].w = tree[v * 2].w + tree[v * 2 + 1].w;
    }

    void downadd(int v) {
        //区间加值lazy=0 标记下传
        tree[v * 2].lazy += tree[v].lazy;
        tree[v * 2 + 1].lazy += tree[v].lazy;
        tree[v * 2].w += tree[v].lazy * (tree[v * 2].r - tree[v * 2].l + 1);
        tree[v * 2 + 1].w += tree[v].lazy * (tree[v * 2 + 1].r - tree[v * 2 + 1].l + 1);
        tree[v].lazy = 0;
    }

    void downupdate(int v) {
        //区间改值lazy=-1 标记下传
        tree[v * 2].lazy = tree[v].lazy;
        tree[v * 2 + 1].lazy = tree[v].lazy;
        tree[v * 2].w = tree[v].lazy * (tree[v * 2].r - tree[v * 2].l + 1);
        tree[v * 2 + 1].w = tree[v].lazy * (tree[v * 2 + 1].r - tree[v * 2 + 1].l + 1);
        tree[v].lazy = -1;
    }


    int ask_point(int v, int x) {
        //单点查询
        if (tree[v].l == tree[v].r) {
            return tree[v].w;
        }

        if (tree[v].lazy != 0) downadd(v);
        //if(tree[v].lazy!=-1) downupdate(v);//区间改值用-1

        int mid = (tree[v].l + tree[v].r) / 2;
        if (x <= mid)
            return ask_point(v * 2, x);

        return ask_point(v * 2 + 1, x);
    }

    void change_point(int v, int x, int y) {
        //单点修改,a[x]改为y(或加减等操作)
        if (tree[v].l == tree[v].r) {
            //tree[k].w+=y;
            tree[v].w = y; //找到了x这个点,a[x]=y,也可进行其他操作
            return;
        }
        if (tree[v].lazy != 0) downadd(v);
        //if(tree[v].lazy!=-1) downupdate(v);//区间改值用-1

        int mid = (tree[v].l + tree[v].r) / 2;
        if (x <= mid)
            change_point(v * 2, x, y);
        else
            change_point(v * 2 + 1, x, y);

        tree[v].w = tree[v * 2].w + tree[v * 2 + 1].w;
    }

    int ask_interval(int v, int a, int b) {
        //区间查询[a,b]
        if (tree[v].l >= a && tree[v].r <= b) {
            return tree[v].w;
        }

        if (tree[v].lazy != 0) downadd(v);
        //if(tree[v].lazy!=-1) downupdate(v);//区间改值用-1

        int sum = 0;
        int mid = (tree[v].l + tree[v].r) / 2;
        if (a <= mid) sum += ask_interval(v * 2, a, b);
        if (b > mid) sum += ask_interval(v * 2 + 1, a, b);

        return sum;
    }

    void changeadd_interval(int v, int a, int b, int y) {
        //区间加值,[a,b]内所有数同时+y
        if (tree[v].l >= a && tree[v].r <= b) {
            tree[v].w += (tree[v].r - tree[v].l + 1) * y;
            tree[v].lazy += y;
            return;
        }
        if (tree[v].lazy != 0) downadd(v);
        //if(tree[v].lazy!=-1) downupdate(v);//区间改值用-1

        int mid = (tree[v].l + tree[v].r) / 2;
        if (a <= mid) changeadd_interval(v * 2, a, b, y);
        if (b > mid) changeadd_interval(v * 2 + 1, a, b, y);

        tree[v].w = tree[v * 2].w + tree[v * 2 + 1].w;
    }

    void changeupdate_interval(int v, int a, int b, int y) {
        //区间改值,[a,b]内所有数同时修改为y
        if (tree[v].l >= a && tree[v].r <= b) {
            tree[v].w = (tree[v].r - tree[v].l + 1) * y;
            tree[v].lazy = y;
            return;
        }
        if (tree[v].lazy != 0) downadd(v);
        //if(tree[v].lazy!=-1) downupdate(v);//区间改值用-1

        int mid = (tree[v].l + tree[v].r) / 2;
        if (a <= mid)
            changeupdate_interval(v * 2, a, b, y);
        if (b > mid)
            changeupdate_interval(v * 2 + 1, a, b, y);

        tree[v].w = tree[v * 2].w + tree[v * 2 + 1].w;
    }


}
